﻿#define _CRT_SECURE_NO_WARNINGS 1
//@[Toc](leetcode)
//# 21. ⼭峰数组的峰顶（easy）
//[题目](https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/574753157/)
//```cpp
//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        //端点是上升得来的
//        //因此端点应该在左区间
//        //左端点的左区间小于等于左端点
//        //左端点的右区间大于左端点
//        int left = 0, right = arr.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid] >= arr[mid - 1])
//                left = mid;
//            else
//                right = mid - 1;
//        }
//        return right;
//    }
//};
//```
//
//# 22. 寻找峰值（medium）
//[题目](https://leetcode.cn/problems/find-peak-element/)
//```cpp
//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] >= nums[mid - 1])
//                left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};
//```
//
//# 23. 搜索旋转排序数组中的最小值（medium）
//[题目](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/submissions/574807382/)
//
//```cpp
//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1, target = nums[nums.size() - 1];
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] > target)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        return nums[right];
//    }
//};
//```
//
//# 24. 0〜n - 1中缺失的数字（easy）
//[题目](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/solutions/)
//```cpp
//class Solution {
//public:
//    int takeAttendance(vector<int>& records) {
//        int left = 0, right = records.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (records[mid] == mid)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        return records[right] == right ? right + 1 : right;
//    }
//};
//```
//
//# 25. 【模板】⼀维前缀和（easy）
//[题目](https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=/exam/oj?page=1&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196)
//```cpp
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, q;
//    cin >> n >> q;
//    vector<int>v(n + 1, 0);
//    for (int i = 1; i < n + 1; i++)
//        cin >> v[i];
//    vector<long long>dp(n + 1, 0);//防止溢出
//    for (int j = 1; j < n + 1; j++)
//        dp[j] = dp[j - 1] + v[j];//下标从1开始保证等式成立，数组大小应为n+1
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}
//
//```